package com.cwj;

/**
 * 背包问题
 * C 为最大体积
 * v 为体积数组
 * w 为权重数组
 * N 为商品个数,N = v.length = w.length
 */
public class Backpack {


    /**
     * 01 背包问题
     */
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                // 不选该物品
                int n = dp[j];
                // 选择该物品
                int y = dp[j - v[i]] + w[i];
                dp[j] = Math.max(n, y);
            }
        }
        return dp[C];
    }

    /**
     * 完全背包
     */
    public int maxValue2(int N, int C, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 1; i < N; i++) {
            int t = w[i - 1];
            for (int j = t; j <= C; j += t) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + t);
            }
        }
        return dp[C];
    }
}
